/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

import java.util.*;

/**
 *
 * @author Administrator
 */
public class LC857 {

    static class Solution {

        /**
         * @param s: a string
         * @param t: a string
         * @return: the minimum substring of S
         */
        public String minWindow(String s, String t) {
            if (s == null || t == null || t.length() == 0 || t.length() > s.length()) {
                return "";
            }

            List<Integer> idexs = new ArrayList<>();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == t.charAt(0)) {
                    idexs.add(i);
                }
            }

            int minwd = Integer.MAX_VALUE;

            String ans = "";
            for (int idx : idexs) {
                String curstr = getcurstr(s, t, idx, minwd);
                int curlen = curstr.length();
                if (!curstr.equals("") && curlen < minwd) {

                    minwd = curlen;
                    ans = curstr;
                }
            }
            return ans;
        }

        public String getcurstr(String s, String t, int idx, int minwd) {
            StringBuilder sb = new StringBuilder();

            int L = idx, R = 0;
            int cnt = 0;
            while (L < s.length() && R < t.length()) {
                if (s.charAt(L) == t.charAt(R)) {
                    R++;
                }
                sb.append(s.charAt(L));
                L++;
                cnt++;
                if (cnt > minwd) { //剪枝
                    return "";
                }
            }

            if (R == t.length()) { //说s[idx]开始出现了子序列可以为t,明有子序列
                return sb.toString();
            }

            return "";
        }

    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.minWindow("jmeqksfrsdcmsiwvaovztaqenprpvnbstl", "u")); //""
        System.out.println(obj.minWindow("abcdebdde", "bde")); //解释："bcde"是答案，"deb"不是一个较小的窗口，因为窗口中的T元素必须按顺序发生。
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有169条未读消息，请及时查看
857 · 最小的窗口子序列
算法
困难
通过率
42%

题目
题解23
笔记
讨论46
排名
记录
描述
给定字符串S和T，在字符串S中找到最小(连续的)子字符串W（窗口），使得T是W的子序列。
如果S中没有包含T中的所有字符的窗口，则返回空字符串""。如果有多个这样的最小长度窗口，则返回一个起点编号最小的。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


输入中的所有字符串只包含小写字母。
S的长度范围在[1, 20000]。
T的长度范围在[1, 100]。
样例
样例 1:

输入：S="jmeqksfrsdcmsiwvaovztaqenprpvnbstl"，T="u"
输出：""
解释： 无法匹配
样例 2:

输入：S = "abcdebdde"， T = "bde"
输出："bcde"
解释："bcde"是答案，"deb"不是一个较小的窗口，因为窗口中的T元素必须按顺序发生。
相关知识
学习《国内大厂高频动规题详解》课程中的22.1国内大厂高频动规题详解：最小的窗口子序列相关内容 ，了解更多相关知识！
标签
企业
Google
易趣
相关题目

32
最小子串覆盖
中等

397
最长上升连续子序列
简单
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
已开启智能提示
发起考试
45 分 00 秒
12345678910
public class Solution {
    /**
     * @param s: a string
     * @param t: a string
     * @return: the minimum substring of S

public String minWindow(String s, String t) {
        // Write your code here
    }

控制台
历史提交

 */
